package com.xigua._递归;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 *
 * @date 2022/3/1019:51
 */
public class _剑指Offer47_礼物的最大价值 {

    // 1 2 5
    // 3 2 1
    public static void main(String[] args) {
        int  grid[][] = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(maxValu1(grid));
    }

    public static int maxValu1(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0 ) grid[i][j] += grid[i][j-1];
                if (j == 0) grid[i][j] += grid[i-1][j];
                if (i != 0 && j !=0) grid[i][j] +=Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m - 1][n - 1];
    }

    public static int maxValue(int[][] grid) {
       return dp(grid,grid.length-1,grid[0].length-1);
    }
    public static int dp(int[][] grid,int i,int j){
        if (i == 0 && j == 0) return grid[i][j];
        if (i == 0 && j != 0) return grid[i][j]+dp(grid,i,j-1);
        if (i != 0 && j == 0) return grid[i][j]+dp(grid,i-1,j);
        return Math.max(dp(grid,i-1,j),dp(grid,i,j-1))+grid[i][j];
    }



}
